﻿#ifndef JEGEO_POLYBOOLOP_HPP
#define JEGEO_POLYBOOLOP_HPP
#include "jegeo/common.hpp"
#include "jegeo/math.hpp"
#include <set>
#include <queue>
#include <QDebug>
#include <QObject>

namespace jegeo {

namespace jemath = jegeo::math;

namespace boolop_internal {

constexpr int E = 50;
const int disE = jemath::roundcast<int, jereal>(jemath::jesqrt(5000));

enum BooleanOpType { INTERSECTION, UNION, DIFFERENCE, XOR };

template<typename T>
inline bool point_left(Point<T> p1, Point<T> p2)
{
    return px(p1) < px(p2) || (px(p1) == px(p2) && py(p1) < py(p2));
}

/*
* 判断矩形和矩形是否相交
*/
template<typename T>
inline bool intersects_rect2rect(const Rect<T> &rect_a, const Rect<T> &rect_b, bool consider_touch = true) {
    return jemath::intersects_rect2rect(px1(rect_a), py1(rect_a), px2(rect_a), py2(rect_a),
                                        px1(rect_b), py1(rect_b), px2(rect_b), py2(rect_b), consider_touch);
}

/*
* ，判断点是否在单调弧或线段的矩形框内
*/
template<typename T>
inline bool point_on_monotony_edge(const T &xs, const T &ys, const T &xe, const T &ye, const T &x, const T &y)
{
    return jemath::is_value_between(x, xs, xe) && (jemath::is_value_between(y, jemath::jemin(ys, ye), jemath::jemax(ys, ye)));
}

/*
* 两个点的距离
*/
template<typename T>
inline T distance(const Point<T> &p1, const Point<T> &p2)
{
    return jemath::distance(px(p1), py(p1), px(p2), py(p2));
}

/*
* 点在两点构成的线段的哪一侧，ps为起点，pe为终点
*/
template<typename T>
inline int point_side(const Point<T> &ps, const Point<T> &pe, const Point<T> &p)
{
    return jemath::orientation_vector2point(px(ps), py(ps), px(pe), py(pe), px(p), py(p));
}

/*
* 点在两点构成的单调圆弧的哪一侧，ps为起点，pe为终点
* 0:表示点在圆上; 1:表示点在圆上侧(左侧); -1:表示点在下侧
*/
template<typename T>
inline int point_side_arc(const Point<T> &ps, const Point<T> &pe, const Point<T> &pc,
                          const T r, const Point<T> &p, bool cw, const T epsilon = disE)
{
    T ymin = jemath::jemin(py(ps), py(pe));
    T ymax = jemath::jemax(py(ps), py(pe));
    if(py(p) < ymin)
        return -1;

    if(py(p) > ymax)
        return 1;

    int side = jemath::orientation_circle2point(px(pc), py(pc), r, px(p), py(p), epsilon);
    return cw ? -side : side;
}

template<typename T>
class JePolygonBoolOp
{
public:
    enum EdgeType { NORMAL, NON_CONTRIBUTING, SAME_TRANSITION, DIFFERENT_TRANSITION };
    enum PolygonType { SUBJECT, CLIPPING };
    enum PositionType { LEFT = 1, RIGHT = -1, ON = 0};

    struct Edge
    {
        Point<T> ps{0, 0};    // 左端点
        Point<T> pe{0, 0};    // 右端点
        Point<T> pc{0, 0};    // 圆弧中心座标
        jereal angle{static_cast<jereal>(0)}; // 圆弧角度
        T radius = std::numeric_limits<T>::max(); // 半径
        Point<T> pstan{std::numeric_limits<T>::max(), 0};
        Point<T> petan{std::numeric_limits<T>::max(), 0};  // 圆弧切线坐标
        bool reversed{false};
        Edge() {}
        Edge(const Vertex<T> &v1, const Vertex<T> &v2);
        inline bool is_arc() const { return jemath::jeabs(angle) > jemath::Epsilon<T>(); }
        inline bool is_cw() const { return angle < -jemath::Epsilon<T>(); }

        void petan_update();
        void pstan_update();
        void radius_update();

        // 判断两个edge是否共线或共弧
        bool collinear(const Edge &other) const;

        // 作为位置比较时的起点
        Point<T> pe_or_petan();
        // 作为位置比较时的终点
        Point<T> ps_or_pstan();
        // 更新(若必要)和获取半径
        T get_radius();

        // 修改某一端点后线段方向变化，用于反转线段
        inline void reverse();
    };

    struct SweepEvent;
    struct EdgeCompare
    {
        bool operator()(SweepEvent *e1, SweepEvent *e2) const;
    };

    struct SweepEvent
    {
        bool isleft{true};
        Point<T> point;
        SweepEvent *pair;
        Edge edge;
        PolygonType polytype;
        EdgeType edgetype;

        //下面的属性只有在事件点是左事件时才有意义
        bool inout{false}; // 该事件在当前X位置的Y方向向下的射线(pos.x, -infinit)是否会发生从多边形内部到外部的变化;
        bool pair_inout{false};
        std::set<SweepEvent *, EdgeCompare>::iterator slit; //sweep line iter
        SweepEvent *prevInResult;                              // previous segment in the result
        bool inResult{false};                                  // is the segment part of the result
        bool resultInOut{false};                               // is the segment part of the result
        unsigned int contourId = 0;
        unsigned int index;

        SweepEvent() {}
        SweepEvent(bool left, Point<T> p, const Edge &e, PolygonType ptype, EdgeType etype = NORMAL)
            : isleft(left)
            , point(p)
            , edge(e)
            , polytype(ptype)
            , edgetype(etype)
            , prevInResult(0)
        {}
        bool isvertical() const { return px(this->point) == px(this->pair->point); }
    };

    struct SweepEventCompare
    {
        bool operator()(SweepEvent *e1, SweepEvent *e2) const;
    };

    JePolygonBoolOp(const Polygon<T> &subj, const Polygon<T> &clip, BooleanOpType op);
    ~JePolygonBoolOp();
    std::vector<Polygon<T>> run(Rect<T> subj_box, Rect<T> clip_box);

private:
    // 根据前一事件计算当前左事件的inout等属性
    void calcEventProps(SweepEvent *le,
                        const typename std::set<SweepEvent *, EdgeCompare>::iterator &previt);
    bool calcInResult(SweepEvent *le);
    int checkIntersection(SweepEvent *le1, SweepEvent *le2);
    void divideEdge(SweepEvent *le, const Point<T> &p);
    void divideEdgeByTwoPoints(SweepEvent *le, const Point<T> &p1, const Point<T> &p2);
    std::vector<Polygon<T>> connectEdges();
    static int nextIndex(int index,
                         const std::vector<SweepEvent *> &resultEvents,
                         const std::vector<bool> &processed);
    SweepEvent *store_event(SweepEvent *evt){
        mAllEvents.push_back(evt);
        return evt;
    }

private:
    const Polygon<T> &mSubject;
    const Polygon<T> &mClipping;
    BooleanOpType mOperation;
    std::priority_queue<SweepEvent *, std::vector<SweepEvent *>, SweepEventCompare> mEvtQueue;
    std::set<SweepEvent *, EdgeCompare> mSweepLines;
    std::vector<SweepEvent *> mAllEvents; // 用于保存所有Event, 便于在运行完成后销毁;
    std::deque<SweepEvent *> mSortedEvents;
    EdgeCompare mEdgeCmp;
    SweepEventCompare mEventCmp;
};


/*
* p1存储第一个交点（若存在至少一个交点），p2存储第二个交点(若存在两个交点）
*/
template<typename T>
inline int intersection_segment2segment(const typename JePolygonBoolOp<T>::Edge &e1, const typename JePolygonBoolOp<T>::Edge &e2,
                                       Point<T> &p1)
{
    // 通过单调性确定x的取值范围不相交(不含仅端点重合)
    if (px(e1.ps) > px(e2.pe) || px(e2.ps) > px(e1.pe))
        return 0;
    // y的取值范围不相交
    if(!jemath::intersects_interval2interval(py(e1.ps), py(e1.pe), py(e2.ps), py(e2.pe)))
        return 0;

    auto &p1x = std::get<0>(p1);
    auto &p1y = std::get<1>(p1);
    int num = jemath::intersection_segment2segment(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe),
                                                  px(e2.ps), py(e2.ps), px(e2.pe), py(e2.pe),
                                                  p1x, p1y);
    if(num == -1) // 平行或共线
    {
        if(!jemath::collinear(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.ps), py(e2.ps))
            || !jemath::collinear(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.pe), py(e2.pe)))
        {
            //平行
            return 0;
        }
        if(point_on_monotony_edge(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.ps), py(e2.ps))
            ||point_on_monotony_edge(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.pe), py(e2.pe))
            ||point_on_monotony_edge(px(e2.ps), py(e2.ps), px(e2.pe), py(e2.pe), px(e1.ps), py(e1.ps))
            ||point_on_monotony_edge(px(e2.ps), py(e2.ps), px(e2.pe), py(e2.pe), px(e1.pe), py(e1.pe)))
            return 3;

        // 直线共线但线段不接触
        return 0;
    }
    else
    {
        // 线和线的起点重合
        if (point::is_equal(e1.ps, e2.ps, E))
            return 0;

        // 线和线的终点重合
        if (point::is_equal(e1.pe, e2.pe, E))
            return 0;

        return num;
    }
}

template<typename T>
inline int intersection_segment2monarc(const typename JePolygonBoolOp<T>::Edge &e1, const typename JePolygonBoolOp<T>::Edge &e2,
                                       Point<T> &p1, Point<T> &p2)
{
    // 线段和弧的起点和终点都重合
    if (point::is_equal(e1.ps, e2.ps, E) && point::is_equal(e1.pe, e2.pe, E)) {
        return 0;
    }
    // 通过单调性确定x的取值范围不相交(不含仅端点重合)
    if (px(e1.ps) > px(e2.pe) || px(e2.ps) > px(e1.pe))
        return 0;
    // y的取值范围不相交
    if(!jemath::intersects_interval2interval(py(e1.ps), py(e1.pe), py(e2.ps), py(e2.pe)))
        return 0;

    auto &p1x = std::get<0>(p1);
    auto &p1y = std::get<1>(p1);
    auto &p2x = std::get<0>(p2);
    auto &p2y = std::get<1>(p2);
    T radius = jemath::jehypot(px(e2.pc) - px(e2.ps), py(e2.pc) - py(e2.ps));
    int num = jemath::intersection_line2circle(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe),
                                                   px(e2.pc), py(e2.pc), radius,
                                                   p1x, p1y, p2x, p2y, E);
    if(num <= 1) // 1为相切
        return 0;
    else
    {
        // 对点进行排序
        if(point_left(p2, p1))
            std::swap(p1, p2);

        if(!(jemath::contains_point_in_monrect(
                px(p1), py(p1), px(e1.ps), jemath::jemin(py(e1.ps), py(e1.pe)), px(e1.pe), jemath::jemax(py(e1.ps), py(e1.pe))
                , true, E))
            ||!(jemath::contains_point_in_monrect(
                px(p1), py(p1), px(e2.ps), jemath::jemin(py(e2.ps), py(e2.pe)), px(e2.pe), jemath::jemax(py(e2.ps), py(e2.pe))
                , true, E)))
        {
            num--;
            // 实际交点仅为p2,所以将p2移到p1上;
            p1 = p2;
        }

        if(!(jemath::contains_point_in_monrect(
                px(p2), py(p2), px(e1.ps), jemath::jemin(py(e1.ps), py(e1.pe)), px(e1.pe), jemath::jemax(py(e1.ps), py(e1.pe))
                , true, E))
            ||!(jemath::contains_point_in_monrect(
                px(p2), py(p2), px(e2.ps), jemath::jemin(py(e2.ps), py(e2.pe)), px(e2.pe), jemath::jemax(py(e2.ps), py(e2.pe))
                , true, E)))
        {
            num--;
        }

        if (num == 0)
            return 0;

        // 此处除了消除交点是端点的情况，还防止计算交点在端点上的误差，即计算结果因为误差导致结果是里端点非常近的点
        // 线和弧的起点重合
        if (point::is_equal(e1.ps, e2.ps, E))
        {
            // 对于起点重合但重合点是两图形的第二个交点的情况，第一个交点一定不是交点，
            // 此时结果num为0，不会因为p2移到p1而出错
            p1 = p2;
            num--;
        }

        // 线和弧的终点重合
        if (point::is_equal(e1.pe, e2.pe, E))
            // 对于终点重合但重合点是两图形的第一个交点的情况，第二个交点一定不是交点，
            // 此时结果num为0，不会因为没有转移点值而出错
            num--;

        return num;
    }
}

template<typename T>
inline int intersection_monarc2monarc(const typename JePolygonBoolOp<T>::Edge &e1, const typename JePolygonBoolOp<T>::Edge &e2,
                                       Point<T> &p1, Point<T> &p2)
{
    // 通过单调性确定x的取值范围不相交(不含仅端点重合)
    if (px(e1.ps) > px(e2.pe) || px(e2.ps) > px(e1.pe))
        return 0;
    // y的取值范围不相交
    if(!jemath::intersects_interval2interval(py(e1.ps), py(e1.pe), py(e2.ps), py(e2.pe)))
        return 0;

    auto &p1x = std::get<0>(p1);
    auto &p1y = std::get<1>(p1);
    auto &p2x = std::get<0>(p2);
    auto &p2y = std::get<1>(p2);
    T radius1 = jemath::jehypot(px(e1.pc) - px(e1.ps), py(e1.pc) - py(e1.ps));
    T radius2 = jemath::jehypot(px(e2.pc) - px(e2.ps), py(e2.pc) - py(e2.ps));
    int num = jemath::intersection_circle2circle(px(e1.pc), py(e1.pc), radius1,
                                                 px(e2.pc), py(e2.pc), radius2,
                                                 p1x, p1y, p2x, p2y, E);

    if(num == 1 || num == 0) //相切或不相交
        return 0;

    if(num == -1) // 共圆
    {
        if((e1.angle > static_cast<jereal>(0)) != (e2.angle > static_cast<jereal>(0)))
            return 0;

        if(point_on_monotony_edge(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.ps), py(e2.ps))
            ||point_on_monotony_edge(px(e1.ps), py(e1.ps), px(e1.pe), py(e1.pe), px(e2.pe), py(e2.pe))
            ||point_on_monotony_edge(px(e2.ps), py(e2.ps), px(e2.pe), py(e2.pe), px(e1.ps), py(e1.ps))
            ||point_on_monotony_edge(px(e2.ps), py(e2.ps), px(e2.pe), py(e2.pe), px(e1.pe), py(e1.pe)))
            return 3;
        return 0;
    }
    else
    {
        if(point_left(p2, p1))
            std::swap(p1, p2);

        if(!(jemath::contains_point_in_monrect(
                px(p1), py(p1), px(e1.ps), jemath::jemin(py(e1.ps), py(e1.pe)), px(e1.pe), jemath::jemax(py(e1.ps), py(e1.pe))
                , true, E))
            ||!(jemath::contains_point_in_monrect(
                px(p1), py(p1), px(e2.ps), jemath::jemin(py(e2.ps), py(e2.pe)), px(e2.pe), jemath::jemax(py(e2.ps), py(e2.pe))
                , true, E)))
        {
            num--;
            // 实际交点仅为p2,所以将p2移到p1上;
            p1 = p2;
        }

        if(!(jemath::contains_point_in_monrect(
                px(p2), py(p2), px(e1.ps), jemath::jemin(py(e1.ps), py(e1.pe)), px(e1.pe), jemath::jemax(py(e1.ps), py(e1.pe))
                , true, E))
            ||!(jemath::contains_point_in_monrect(
                px(p2), py(p2), px(e2.ps), jemath::jemin(py(e2.ps), py(e2.pe)), px(e2.pe), jemath::jemax(py(e2.ps), py(e2.pe))
                , true, E)))
        {
            num--;
        }

        // 无交点
        if (num == 0)
            return 0;

        // 弧的起点重合
        if (point::is_equal(e1.ps, e2.ps, E))
        {
            // 实际交点仅为p2,所以将p2移到p1上;
            p1 = p2;
            num--;
        }

        // 弧的终点重合
        if (point::is_equal(e1.pe, e2.pe, E))
           num--;

        return num;
    }
}

template<typename T>
struct ResultContour
{
    Polyline<T> path;
    std::vector<std::pair<int, ResultContour<T>*>> children;
    bool external = true;
    int mOrientation = 0;
    PolylineList<T> allPaths() const
    {
        PolylineList<T> result;
        auto p = path;
        polyline::set_hole(p, !external);
        result.push_back(p);
        if(this->external)
        {
            for (auto &child : children) {
                auto childPaths = child.second->allPaths();
                result.insert(result.end(), childPaths.begin(), childPaths.end());
            }
        }
        return result;
    }

    Polygon<T> toSurface() const
    {
        Polygon<T> surface;
        auto paths = allPaths();
        for (auto &path : paths) {
            polygon::add_subpath(surface, path);
        }
        return surface;
    }

    void reverseOrientation()
    {
        std::reverse(polyline::vertices(path).begin(), polyline::vertices(path).end());
        for (auto iter = polyline::vertices(path).end() - 1; iter != polyline::vertices(path).begin(); iter--) {
            set_angle(*iter, -vertex::get_angle(*(prev(iter))));
        }
        set_angle(polyline::first_vertex(path), std::numeric_limits<jereal>::quiet_NaN());
        this->mOrientation = -this->mOrientation;
    }

    bool isCw()
    {
        if (mOrientation == 0) {
            jereal sum = 0.0;
            for (int i = 0; i < polyline::verteics_count(path) - 1; i++) {
                auto v1 = polyline::vertex_at(path, i);
                auto v2 = polyline::vertex_at(path, (i+1) % (polyline::verteics_count(path) - 1));
                sum += math::jemul(px(vertex::get_pos(v1)) - px(vertex::get_pos(v2)), py(vertex::get_pos(v2)) + py(vertex::get_pos(v1)));
            }
            if (sum > 0.0)
                mOrientation = 1;
            else if (sum < 0.0)
                mOrientation = -1;
        }
        return mOrientation == -1;
    }

};

template<typename T>
bool JePolygonBoolOp<T>::Edge::collinear(const Edge &other) const
{
    if(this->is_arc() != other.is_arc())
        return false;

    auto p1 = this->ps;
    auto p2 = this->pe;
    auto p3 = other.ps;
    auto p4 = other.pe;
    if (this->is_arc()) {
        auto pc = this->pc;
        if (point::not_equal(pc, other.pc, E))
            return false;

        T dis = jemath::jehypot(px(other.pc) - px(p3), py(other.pc) - py(p3));
        T r = jemath::jehypot(px(pc) - px(p1), py(pc) - py(p1));
        if (!jemath::fuzzy_equal(dis, r, disE))
            return false;
        return (point_on_monotony_edge(px(p1), py(p1), px(p2), py(p2), px(p3), py(p3))
                || point_on_monotony_edge(px(p1), py(p1), px(p2), py(p2), px(p4), py(p4))
                || point_on_monotony_edge(px(p3), py(p3), px(p4), py(p4), px(p1), py(p1))
                || point_on_monotony_edge(px(p3), py(p3), px(p4), py(p4), px(p2), py(p2)));
    } else {
        return (jemath::collinear(px(p1), py(p1), px(p2), py(p2), px(p3), py(p3))
                && jemath::collinear(px(p1), py(p1), px(p2), py(p2), px(p4), py(p4)));
    }
}

template<typename T>
JePolygonBoolOp<T>::Edge::Edge(const Vertex<T> &v1, const Vertex<T> &v2)
{
    if (point_left(vertex::get_pos(v1), vertex::get_pos(v2))) {
        set_px(ps, px(v1));
        set_py(ps, py(v1));
        set_px(pe, px(v2));
        set_py(pe, py(v2));
        angle = vertex::get_angle(v2);
        reversed = false;
    } else {
        set_px(ps, px(v2));
        set_py(ps, py(v2));
        set_px(pe, px(v1));
        set_py(pe, py(v1));
        angle = -vertex::get_angle(v2);
        reversed = true;
    }

    if(is_arc())
    {
        // 对特别小的弧的处理，由于是单调弧，起点和终点的xy值应都不同，若计算误差导致相同，将其改为直线
        // 角度统一为jereal类型
        if(jemath::fuzzy_equal(px(ps), px(pe)) || jemath::fuzzy_equal(py(ps), py(pe)))
            angle = static_cast<jereal>(0);
        else
        {
            auto &pcx = std::get<0>(pc);
            auto &pcy = std::get<1>(pc);
            jemath::arc_center_from_angle<T>(px(ps), py(ps), px(pe), py(pe), angle, pcx, pcy);

            // 防止计算误差导致形成过象限弧
            if(px(pc) - px(ps) > static_cast<T>(0) && px(pc) - px(pe) < static_cast<T>(0))
                jemath::jeabs(px(pc) - px(ps)) < jemath::jeabs(px(pc) - px(pe)) ? set_px(pc, px(ps)) : set_px(pc, px(pe));
            if(angle > static_cast<jereal>(0) ? py(pc) < py(ps) : py(pc) > py(ps))
                set_py(pc, py(ps));
        }
    }
}

template<typename T>
void JePolygonBoolOp<T>::Edge::petan_update()
{
    if (is_arc()) {
        // 计算切线与终点所在直线的交点，主要用于判断圆弧直接的上下位置关系
        // 计算直线时，视情况考虑水平方向还是垂直方向;
        if (jemath::fuzzy_equal(px(ps), px(pc))) {
            set_px(petan, px(pe));
            set_py(petan, py(ps));
        } else if (jemath::fuzzy_equal(py(ps), py(pc))) {
            set_px(petan, px(ps));
            set_py(petan, py(pe));
        } else {
            if(px(pc) <= px(ps))
            {
                set_px(petan, px(pe));
                set_py(petan, py(ps) - jemath::roundcast<T, jereal>(
                              jemath::jediv(jemath::jemul(px(ps) - px(pc), px(petan) - px(ps)), py(ps) - py(pc))));
            }
            else
            {
                set_py(petan, py(pe));
                set_px(petan, (px(ps)) - jemath::roundcast<T, jereal>(
                              jemath::jediv(jemath::jemul(py(ps) - py(pc), py(petan) - py(ps)), px(ps) - px(pc))));
            }
        }
    }
}

template<typename T>
void JePolygonBoolOp<T>::Edge::pstan_update()
{
    if (is_arc()) {
        if (jemath::fuzzy_equal(px(pe), px(pc))) {
            set_px(pstan, px(ps));
            set_py(pstan, py(pe));
        } else if (jemath::fuzzy_equal(py(pe), py(pc))) {
            set_px(pstan, px(pe));
            set_py(pstan, py(ps));
        } else {
            if(px(pc) > px(ps))
            {
                set_px(pstan, px(ps));
                set_py(pstan, py(pe) - jemath::roundcast<T, jereal>(
                              jemath::jediv(jemath::jemul(px(pe) - px(pc), px(pstan) - px(pe)), py(pe) - py(pc))));
            }
            else
            {
                set_py(pstan, py(ps));
                set_px(pstan, px(pe) - jemath::roundcast<T, jereal>(
                              jemath::jediv(jemath::jemul(py(pe) - py(pc), py(pstan) - py(pe)), px(pe) - px(pc))));
            }
        }
    }
}

template<typename T>
void JePolygonBoolOp<T>::Edge::radius_update()
{
    radius = jemath::jehypot(px(pc) - px(ps), py(pc) - py(ps));
}

template<typename T>
Point<T> JePolygonBoolOp<T>::Edge::pe_or_petan()
{
    if(is_arc())
    {
        if(px(petan) == std::numeric_limits<T>::max())
        {
            petan_update();
            return petan;
        }
        return petan;
    }
    return pe;
}

template<typename T>
Point<T> JePolygonBoolOp<T>::Edge::ps_or_pstan()
{
    if(is_arc())
    {
        if(px(pstan) == std::numeric_limits<T>::max())
        {
            pstan_update();
            return pstan;
        }
        return pstan;
    }
    return ps;
}

template<typename T>
T JePolygonBoolOp<T>::Edge::get_radius()
{
    if(radius == std::numeric_limits<T>::max())
    {
        radius_update();
        return radius;
    }
    return radius;
}

template<typename T>
void JePolygonBoolOp<T>::Edge::reverse()
{
    std::swap(ps, pe);
    angle = -angle;
    reversed = !reversed;
}


template<typename T>
bool JePolygonBoolOp<T>::SweepEventCompare::operator()(SweepEvent *e1, SweepEvent *e2) const
{
    // 排序规则: priority_queue中的比较规则与std::sort中的比较是相反的，return true的排在后面；
    // 1. pos X小的排前面
    // 2. X一样，则Y小的排前面
    // 3. X.Y都一样，则右事件(退出事件)排前面，左事件(进入事件)排后面
    // 4. 如果X.Y一样，事件类型也一样，说明可能是同一个出发点或结束点,一般发生在一个多边形开始或封闭结束时，
    //    此时，看事件的另一个两条线是否共线，
    //         如果不共线：则事件对应的segment位于下方的排前面
    //         如果共线：（同一个多边形是不允许出现的）因此，clipping类型的多边形排后面，subject排前面

    // 如果事件点位不一样，则点位x,y大的排后面
    if (jemath::fuzzy_greaterequal(px(e1->point) > px(e2->point)))
        return true;
    if (px(e2->point) > px(e1->point))
        return false;
    if (py(e1->point) != py(e2->point))
        return py(e1->point) > py(e2->point);

    // 如果事件点位一样，事件类型不一样，则右事件的排前面, 因为在处理时需要先处理退出事件
    if (e1->isleft != e2->isleft)
        return e1->isleft;
    // 如果事件点位一样，事件类型也一样，并且不共线不共弧，则看对应在segment的上下关系，
    // 分成三种情况，线和线，线和弧，弧和弧
    // 线和线
    if(!e1->edge.is_arc() && !e2->edge.is_arc())
    {
        // 不共线
        if (!e1->edge.collinear(e2->edge))
        { //point_side表示点在线的哪一侧，right表示右侧，即线段在点的上面，left表示左侧，即线段在点的下面，
            return point_side(e1->edge.ps, e1->edge.pe, e2->pair->point) == RIGHT;
        }

        // 共线
        if (e1->polytype != e2->polytype)
            return e1->polytype > e2->polytype;

        // 对计算误差或错误输入的处理
        return e1 < e2;
    }

    // 弧和弧
    if (e1->edge.is_arc() && e2->edge.is_arc())
    {
        // 不共弧
        if (!e1->edge.collinear(e2->edge))
        {
            // 圆弧方向相同
            // 起点相同
            if (e1->isleft)
            {
                int side = point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.pe_or_petan());
                if(side == ON)
                {
                    return point_side_arc(e1->edge.ps, e1->edge.pe, e1->edge.pc,
                                          e1->edge.get_radius(), e2->edge.pe, e1->edge.is_cw()) == RIGHT;
                }
                return side == RIGHT;
            }
            // 终点相同
            int side = point_side(e1->edge.ps_or_pstan(), e1->edge.pe, e2->edge.ps_or_pstan());
            if(side == ON)
                return point_side_arc(e1->edge.ps, e1->edge.pe, e1->edge.pc,
                                      e1->edge.get_radius(), e2->edge.ps, e1->edge.is_cw()) == RIGHT;
            return side == RIGHT;
        }

        // 共弧
        // 圆弧方向不同
        if ((e1->edge.angle > jemath::Epsilon<jereal>() && e2->edge.angle < -jemath::Epsilon<jereal>())
            || (e1->edge.angle < -jemath::Epsilon<jereal>() && e2->edge.angle > jemath::Epsilon<jereal>()))
            return e1->edge.angle < -jemath::Epsilon<jereal>();

        // 圆弧方向相同
        if (e1->polytype != e2->polytype)
            return e1->polytype > e2->polytype;

        // 对计算误差或错误输入的处理
        return e1 < e2;
    }

    // 线和弧
    // 起点相同
    if(e1->isleft)
    {
        int side = point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.pe_or_petan());
        // 圆弧和线相切，切点为事件点
        if (side == ON)
            return point_side(e1->edge.ps, e1->edge.pe, e2->edge.pe)
                   == RIGHT;
        // 不相切
        return side == RIGHT;
    }

    // 终点相同
    int side = point_side(e1->edge.ps_or_pstan(), e1->edge.pe, e2->edge.ps_or_pstan());
    if (side == ON)
        return point_side(e1->edge.ps, e1->edge.pe, e2->edge.ps)
               == RIGHT;
    return side == RIGHT;

}

template<typename T>
bool JePolygonBoolOp<T>::EdgeCompare::operator()(SweepEvent *e1, SweepEvent *e2) const
{
    // 排序规则: 这个排序是对set排序，是正常从小到大排，注意与SweepEventCompare是相反的；
    // 排序中只会出现左事件，小(true)的表示在下方，即从小到大表示线段从下往上。
    // if(e1->edge.is_arc())
    //     qDebug() << distance(e1->point, e1->edge.pc) << distance(e1->pair->point, e1->edge.pc);
    if (e1 == e2)
        return false;
    if (!e1->edge.collinear(e2->edge)) {
        // 两个线段不共线或共弧
        // 如果两个事件位置一样，则看Segment别端在下面的排前面
        if (point::is_equal(e1->point, e2->point, static_cast<T>(0))) {
            // 线与线
            if (!e1->edge.is_arc() && !e2->edge.is_arc())
                return point_side(e1->edge.ps, e1->edge.pe, e2->edge.pe)
                       == LEFT;

            // 弧与弧
            if (e1->edge.is_arc() && e2->edge.is_arc())
            {
                int side = point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.pe_or_petan());
                if (side == ON)
                // 起点引出的切线共线
                    return point_side_arc(e1->edge.ps, e1->edge.pe, e1->edge.pc,
                                      e1->edge.get_radius(), e2->edge.pe, e1->edge.is_cw()) == LEFT;
                return side == LEFT;
            }

            //线与弧
            int side = point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.pe_or_petan());
            if (side == ON)
                return point_side(e1->edge.ps, e1->edge.pe, e2->edge.pe)
                       == LEFT;
            return side == LEFT;
        }
        // 如果X相同，Y不同，Y小的排前面
        if (px(e1->point) == px(e2->point)) {
            return py(e1->point) < py(e2->point);
        }
        // 如果X不相同，则按事件
        SweepEventCompare comp;
        // 靠左事件对应的线段在靠右事件对应的点的相对位置

        // 当左事件为圆弧，右事件为线段或朝向相反的圆弧，若右事件对应线或弧在左事件对应弧外侧时
        // 单纯比较线段上下可能会出错，需要另外处理!!!
        if (comp(e1, e2)) {
            // 线与线
            if (!e1->edge.is_arc() && !e2->edge.is_arc())
            {
                int side = point_side(e2->edge.ps, e2->edge.pe, e1->edge.ps);
                if(side == ON)
                {
                    return point_side(e2->edge.ps, e2->edge.pe, e1->edge.pe) == RIGHT;
                }
                return side == RIGHT;
            }

            // 至少有一段是弧
            // bool outside;
            // if (e2->edge.is_arc())
            // {
            //     bool a = e2->edge.is_cw() ? py(e1->point) >= jemath::jemin(py(e2->edge.ps), py(e2->edge.pe))
            //                               : py(e1->point) <= jemath::jemax(py(e2->edge.ps), py(e2->edge.pe));
            //     outside = a && distance(e1->point, e2->edge.pc) >= distance(e2->point, e2->edge.pc) - 1;
            // }
            // else
            // {
            //     bool a = e1->edge.is_cw() ? py(e2->point) >= jemath::jemin(py(e1->edge.ps), py(e1->edge.pe))
            //                               : py(e2->point) <= jemath::jemax(py(e1->edge.ps), py(e1->edge.pe));
            //     outside = a && distance(e2->point, e1->edge.pc) >= distance(e1->point, e1->edge.pc) - 1;
            // }

            // if(outside)
            // {
            //     return point_side(e2->edge.ps, e2->edge.pe, e1->edge.ps) == RIGHT;
            // }
            // return point_side(e2->edge.ps, e2->edge.pe_or_petan(), e1->edge.ps) == RIGHT;

            if (e2->edge.is_arc())
            {
                int side = point_side_arc(e2->edge.ps, e2->edge.pe, e2->edge.pc,
                                          e2->edge.get_radius(), e1->edge.ps, e2->edge.is_cw());
                if(side == 0)
                {
                    Point<T> petan1 = e1->edge.pe_or_petan();
                    jereal angle = jemath::arc_degree_from_secw(px(e2->edge.pc), py(e2->edge.pc), px(petan1), py(petan1),
                                                 px(e1->edge.ps), py(e1->edge.ps), !e2->edge.is_cw());
                    return jemath::jeabs(angle) > 90;
                }
                return side == RIGHT;
            }
            return point_side(e2->edge.ps, e2->edge.pe, e1->edge.ps) == RIGHT;
        }

        if (!e1->edge.is_arc() && !e2->edge.is_arc())
        {
            int side = point_side(e1->edge.ps, e1->edge.pe, e2->edge.ps);
            if(side == ON)
            {
                return point_side(e1->edge.ps, e1->edge.pe, e2->edge.pe) == LEFT;
            }
            return side  == LEFT;
        }

        // !!!
        // bool outside;
        // if (e1->edge.is_arc())
        // {
        //     bool a = e1->edge.is_cw() ? py(e2->point) >= jemath::jemin(py(e1->edge.ps), py(e1->edge.pe))
        //                               : py(e2->point) <= jemath::jemax(py(e1->edge.ps), py(e1->edge.pe));
        //     outside = a && distance(e2->point, e1->edge.pc) >= distance(e1->point, e1->edge.pc) - 1;
        // }
        // else
        // {
        //     bool a = e2->edge.is_cw() ? py(e2->point) >= jemath::jemin(py(e1->edge.ps), py(e1->edge.pe))
        //                               : py(e2->point) <= jemath::jemax(py(e1->edge.ps), py(e1->edge.pe));
        //     outside = a && distance(e1->point, e2->edge.pc) >= distance(e2->point, e2->edge.pc) - 1;
        // }

        // if(outside)
        // {
        //     return point_side(e1->edge.ps, e1->edge.pe, e2->edge.ps) == LEFT;
        // }
        // return point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.ps) == LEFT;

        if (e1->edge.is_arc())
        {
            int side = point_side_arc(e1->edge.ps, e1->edge.pe, e1->edge.pc,
                                      e1->edge.get_radius(), e2->edge.ps, e1->edge.is_cw());
            if(side == 0)
            {
                Point<T> petan2 = e2->edge.pe_or_petan();
                jereal angle = jemath::arc_degree_from_secw(px(e1->edge.pc), py(e1->edge.pc), px(petan2), py(petan2),
                                                            px(e2->edge.ps), py(e2->edge.ps), !e1->edge.is_cw());
                return jemath::jeabs(angle) < 90;
            }
            return side == LEFT;
        }
        return point_side(e1->edge.ps, e1->edge.pe_or_petan(), e2->edge.ps) == LEFT;
    }

    // 如果共线或共弧
    if ((e1->edge.angle > jemath::Epsilon<jereal>() && e2->edge.angle < -jemath::Epsilon<jereal>())
        || (e1->edge.angle < -jemath::Epsilon<jereal>() && e2->edge.angle > jemath::Epsilon<jereal>()))
        return e1->edge.angle > jemath::Epsilon<jereal>();

    if (e1->polytype != e2->polytype) {
        return e1->polytype < e2->polytype;
    }

    // Just a consistent criterion is used
    if (point::is_equal(e1->point, e2->point, static_cast<T>(0))) {
        return e1 < e2;
    }

    SweepEventCompare comp;
    return comp(e1, e2);
}

template<typename T>
void JePolygonBoolOp<T>::divideEdge(SweepEvent *le, const Point<T> &p)
{
    // 一个交点的情况下分割线段
    Point<T> ps(le->edge.ps);
    SweepEvent *r;
    SweepEvent *l;
    if (le->edge.is_arc()) {
        // 计算分割后弧的角度
        Point<T> pc(le->edge.pc);
        T x = px(p);
        T y = py(p);
        T xs = px(ps);
        T ys = py(ps);
        T xc = px(pc);
        T yc = py(pc);

        jereal left_angle = jemath::arc_degree_from_secw(xs, ys, x, y, xc, yc, le->edge.is_cw());

        // 将切出的过小的弧变为直线
        if(jemath::fuzzy_equal(xs, x) || jemath::fuzzy_equal(ys, y))
            left_angle = static_cast<jereal>(0);
        jereal right_angle =le->edge.angle - left_angle;
        if(jemath::fuzzy_equal(px(le->edge.pe), x) || jemath::fuzzy_equal(py(le->edge.pe), y))
            right_angle = static_cast<jereal>(0);

        le->edge.angle = left_angle;
        le->edge.pe = p;
        set_px(le->edge.petan, std::numeric_limits<T>::max());
        set_px(le->edge.pstan, std::numeric_limits<T>::max());
        if(point_left(le->edge.pe, le->edge.ps))
        {
            // 前置的误差处理可能导致线段方向变化，此时进行反转
            le->edge.reverse();
            le->point = le->edge.ps;
        }
        r = store_event(new SweepEvent(false, le->edge.pe, le->edge, le->polytype));

        le->pair->edge.angle = right_angle;
        le->pair->edge.ps = p;
        set_px(le->pair->edge.petan, std::numeric_limits<T>::max());
        set_px(le->pair->edge.pstan, std::numeric_limits<T>::max());
        if(point_left(le->pair->edge.pe, le->pair->edge.ps))
        {
            le->pair->edge.reverse();
            le->pair->point = le->edge.pe;
        }
        l = store_event(new SweepEvent(true, le->pair->edge.ps, le->pair->edge, le->pair->polytype));

        r->pair = le;
        l->pair = le->pair;
    } else {
        // 左侧线段右事件
        le->edge.pe = p;
        r = store_event(new SweepEvent(false, p, le->edge, le->polytype));
        // 右侧线段左事件
        le->pair->edge.ps = p;
        l = store_event(new SweepEvent(true, p, le->pair->edge, le->pair->polytype));

        r->pair = le;
        l->pair = le->pair;
    }

    // if (mSegmentCmp(l, le->pair)) {
    //     // avoid a rounding error. The left event would be processed after the right event
    //     qDebug() << "Oops" << Qt::endl;
    //     // le->pair->isleft = true;
    //     // l->isleft = false;
    // }
    // if (mSegmentCmp(le, r)) {
    //     // avoid a rounding error. The left event would be processed after the right event
    //     qDebug() << "Oops2" << Qt::endl;
    // }

    le->pair->pair = l;
    le->pair = r;
    mEvtQueue.push(l);
    mEvtQueue.push(r);
}

template<typename T>
void JePolygonBoolOp<T>::divideEdgeByTwoPoints(SweepEvent *le, const Point<T> &p1, const Point<T> &p2)
{
    // 两个交点的情况下分割线段(分成三段)
    SweepEvent *lr, *ml, *mr, *rl;
    if (le->edge.is_arc()) {
        // 计算分割后弧的角度
        Point<T> ps = le->edge.ps;
        Point<T> pc = le->edge.pc;
        T x1 = px(p1);
        T y1 = py(p1);
        T x2 = px(p2);
        T y2 = py(p2);
        T xs = px(ps);
        T ys = py(ps);
        T xc = px(pc);
        T yc = py(pc);

        bool cw = le->edge.is_cw();
        jereal left_angle = jemath::arc_degree_from_secw(xs, ys, x1, y1, xc, yc, cw);
        jereal middle_angle = jemath::arc_degree_from_secw(x1, y1, x2, y2, xc, yc, cw);

        if(jemath::fuzzy_equal(xs, x1) || jemath::fuzzy_equal(ys, y1))
            left_angle = static_cast<jereal>(0);
        if(jemath::fuzzy_equal(x1, x2) || jemath::fuzzy_equal(y1, y2))
            middle_angle = static_cast<jereal>(0);
        T right_angle = le->edge.angle - left_angle - middle_angle;
        if(jemath::fuzzy_equal(x2, px(le->edge.pe)) || jemath::fuzzy_equal(y1, py(le->edge.pe)))
            right_angle = static_cast<jereal>(0);

        Edge me(le->edge);
        le->edge.angle = left_angle;
        le->edge.pe = p1;
        set_px(le->edge.petan, std::numeric_limits<T>::max());
        set_px(le->edge.pstan, std::numeric_limits<T>::max());
        if(point_left(le->edge.pe, le->edge.ps))
        {
            le->edge.reverse();
            le->point = le->edge.ps;
        }
        lr = store_event(new SweepEvent(false, le->edge.pe, le->edge, le->polytype));

        me.ps = p1;
        me.pe = p2;
        me.angle = middle_angle;
        set_px(me.petan, std::numeric_limits<T>::max());
        set_px(me.pstan, std::numeric_limits<T>::max());
        if(point_left(me.pe, me.ps))
            me.reverse();
        ml = store_event(new SweepEvent(true, p1, me, le->polytype));
        mr = store_event(new SweepEvent(false, p2, me, le->polytype));

        le->pair->edge.ps = p2;
        le->pair->edge.angle = right_angle;
        set_px(le->pair->edge.petan, std::numeric_limits<T>::max());
        set_px(le->pair->edge.pstan, std::numeric_limits<T>::max());
        if(point_left(le->pair->edge.pe, le->pair->edge.ps))
        {
            le->pair->edge.reverse();
            le->pair->point = le->edge.pe;
        }
        rl = store_event(
            new SweepEvent(true, le->pair->edge.ps, le->pair->edge, le->pair->polytype));
    } else {
        // 左侧部分右事件
        Edge me = le->edge;
        le->edge.pe = p1;
        lr = store_event(new SweepEvent(false, p1, le->edge, le->polytype));
        // 中间部分左事件
        me.ps = p1;
        me.pe = p2;
        ml = store_event(new SweepEvent(true, p1, me, le->polytype));
        // 中间部分右事件
        mr = store_event(new SweepEvent(false, p2, me, le->polytype));
        // 右侧部分左事件
        le->pair->edge.ps = p2;
        rl = store_event(new SweepEvent(true, p2, le->pair->edge, le->pair->polytype));
    }
    lr->pair = le;
    ml->pair = mr;
    mr->pair = ml;
    rl->pair = le->pair;
    le->pair->pair = rl;
    le->pair = lr;
    mEvtQueue.push(lr);
    mEvtQueue.push(ml);
    mEvtQueue.push(mr);
    mEvtQueue.push(rl);
}

// 寻找edge的切分点，与一般求交点不同，仅端点重合以及相切的情况不需要切分，所以视为不相交
template<typename T>
int JePolygonBoolOp<T>::checkIntersection(SweepEvent *le1, SweepEvent *le2)
{
    Point<T> pi1;
    Point<T> pi2;
    Edge edge1(le1->edge);
    Edge edge2(le2->edge);
    int ipNum; // 有效交点数，取0到2，共线和共弧的特殊情况取3

    if (!(edge1.is_arc() or edge2.is_arc())) {
        ipNum = intersection_segment2segment(edge1, edge2, pi1);
    } else {
        if (edge1.is_arc() && edge2.is_arc()) {
            ipNum = intersection_monarc2monarc(edge1, edge2, pi1, pi2);
        } else {
            if (edge2.is_arc())
                ipNum = intersection_segment2monarc(edge1, edge2, pi1, pi2);
            else
                ipNum = intersection_segment2monarc(edge2, edge1, pi1, pi2);
        }
    }

    if (ipNum <= 0)
        return 0; // 不相交

    if (ipNum == 2 && le1->polytype == le2->polytype)
        exit(1); // 同一线段或弧相交，不合法的情况

    // 交点接近端点时修正为端点
    if(ipNum < 3)
    {
        if(point::is_equal(le1->point, pi1, E))
            pi1 = le1->point;
        else if(point::is_equal(le1->pair->point, pi1, E))
            pi1 = le1->pair->point;
        else if(point::is_equal(le2->point, pi1, E))
            pi1 = le2->point;
        else if(point::is_equal(le2->pair->point, pi1, E))
            pi1 = le2->pair->point;

        if(ipNum > 1)
        {
            if(point::is_equal(le1->point, pi2, E))
                pi2 = le1->point;
            else if(point::is_equal(le1->pair->point, pi2, E))
                pi2 = le1->pair->point;
            else if(point::is_equal(le2->point, pi2, E))
                pi2 = le2->point;
            else if(point::is_equal(le2->pair->point, pi2, E))
                pi2 = le2->pair->point;
        }
    }

    //有一个交点
    if (ipNum == 1) {
        if (point::not_equal(le1->point, pi1)
            && point::not_equal(le1->pair->point, pi1)) // 交点不为l1的端点
            divideEdge(le1, pi1);
        if (point::not_equal(le2->point, pi1)
            && point::not_equal(le2->pair->point, pi1)) // 交点不为l2的端点
            divideEdge(le2, pi1);
        return 1;
    }

    // 共线或共弧
    if (ipNum == 3) {
        std::vector<SweepEvent *> sortedEvents;
        if (point::is_equal(le1->point, le2->point, E))
            sortedEvents.push_back(0);
        else {
            if (mEventCmp(le1, le2)) {
                sortedEvents.push_back(le2);
                sortedEvents.push_back(le1);
            } else {
                sortedEvents.push_back(le1);
                sortedEvents.push_back(le2);
            }
        }

        if (point::is_equal(le1->pair->point, le2->pair->point, E))
            sortedEvents.push_back(0);
        else {
            if (mEventCmp(le1->pair, le2->pair)) {
                sortedEvents.push_back(le2->pair);
                sortedEvents.push_back(le1->pair);
            } else {
                sortedEvents.push_back(le1->pair);
                sortedEvents.push_back(le2->pair);
            }
        }

        if ((sortedEvents.size() == 2) || (sortedEvents.size() == 3 && sortedEvents[2])) {
            // 线段或弧完全重合或左端点相同
            le1->edgetype = NON_CONTRIBUTING;
            le2->edgetype = (le1->inout == le2->inout) ? SAME_TRANSITION : DIFFERENT_TRANSITION;
            if (sortedEvents.size() == 3)
                divideEdge(sortedEvents[2]->pair, sortedEvents[1]->point);
            return 2;
        }
        if (sortedEvents.size() == 3) {
            // 左端点不同但右端点相同
            divideEdge(sortedEvents[0], sortedEvents[1]->point);
            return 3;
        }
        if (sortedEvents[0] != sortedEvents[3]->pair) {
            // 互相不包含
            divideEdge(sortedEvents[0], sortedEvents[1]->point);
            divideEdge(sortedEvents[1], sortedEvents[2]->point);
            return 3;
        }
        // 一个包含另一个
        divideEdge(sortedEvents[0], sortedEvents[1]->point);
        divideEdge(sortedEvents[3]->pair, sortedEvents[2]->point);
        return 3;
    }

    // 有两个交点但不共线共弧
    bool p1Inle1 = point::not_equal(le1->point, pi1) && point::not_equal(le1->pair->point, pi1); // pi1不为l1的端点
    bool p2Inle1 = point::not_equal(le1->point, pi2) && point::not_equal(le1->pair->point, pi2); // pi2不为l1的端点
    bool p1Inle2 = point::not_equal(le2->point, pi1) && point::not_equal(le2->pair->point, pi1); // pi1不为l2的端点
    bool p2Inle2 = point::not_equal(le2->point, pi2) && point::not_equal(le2->pair->point, pi2); // pi2不为l2的端点
    if (p1Inle1 && p2Inle1)
        divideEdgeByTwoPoints(le1, pi1, pi2);
    else if(p1Inle1 && !p2Inle1)
        divideEdge(le1, pi1);
    else if(!p1Inle1 && p2Inle1)
        divideEdge(le1, pi2);

    if (p1Inle2 && p2Inle2)
        divideEdgeByTwoPoints(le2, pi1, pi2);
    else if(p1Inle2 && !p2Inle2)
        divideEdge(le2, pi1);
    else if(!p1Inle2 && p2Inle2)
        divideEdge(le2, pi2);

    return 1;
}

template<typename T>
void JePolygonBoolOp<T>::calcEventProps(
    SweepEvent *le, const typename std::set<SweepEvent*, EdgeCompare>::iterator &previt)
{
    if (previt == mSweepLines.end()) {
        le->inout = false;
        le->pair_inout = true;
    } else if (le->polytype == (*previt)->polytype) {
        le->inout = !(*previt)->inout;
        le->pair_inout = (*previt)->pair_inout;
    } else {
        le->inout = !(*previt)->pair_inout;
        le->pair_inout = (*previt)->isvertical() ? !(*previt)->inout : (*previt)->inout;
    }

    if (previt != mSweepLines.end())
        le->prevInResult = (!calcInResult(*previt) || (*previt)->isvertical())
                               ? (*previt)->prevInResult
                               : *previt;

    le->inResult = calcInResult(le);
    Point<T> s = le->edge.ps;
    Point<T> e = le->edge.pe;
    qDebug() << le->inResult << le->polytype << "ps(" << px(s) << "," << py(s) << ") pe(" << px(e) << "," << py(e)
             << ") angle:" << le->edge.angle << Qt::endl;

}

template<typename T>
bool JePolygonBoolOp<T>::calcInResult(SweepEvent *le)
{
    switch (le->edgetype) {
    case NORMAL:
        switch (mOperation) {
        case (INTERSECTION):
            return !le->pair_inout;
        case (UNION):
            return le->pair_inout;
        case (DIFFERENCE):
            return (le->polytype == SUBJECT && le->pair_inout)
                   || (le->polytype == CLIPPING && !le->pair_inout);
        case (XOR):
            return true;
        }
    case SAME_TRANSITION:
        return mOperation == INTERSECTION || mOperation == UNION;
    case DIFFERENT_TRANSITION:
        return mOperation == DIFFERENCE;
    case NON_CONTRIBUTING:
        return false;
    }
    return false; // just to avoid the compiler warning
}

template<typename T>
int JePolygonBoolOp<T>::nextIndex(int index,
                                  const std::vector<SweepEvent *> &resultEvents,
                                  const std::vector<bool> &processed)
{
    unsigned int newIndex = index + 1;
    while (newIndex < resultEvents.size()
           && point::is_equal(resultEvents[newIndex]->point, resultEvents[index]->point)) {
        if (!processed[newIndex])
            return newIndex;
        else
            ++newIndex;
    }
    if((newIndex = index - 1) == -1)
        return -1;
    while (processed[newIndex]) {
        --newIndex;
        // 非闭合曲线终点和起点不同
        if(newIndex == -1)
            return -1;
    }
    return newIndex;
}

template<typename T>
std::vector<Polygon<T>> JePolygonBoolOp<T>::connectEdges()
{
    std::vector<SweepEvent *> resultEvents;
    resultEvents.reserve(mSortedEvents.size());
    for (auto iter : mSortedEvents) {
        if ((iter->isleft && iter->inResult) || (!iter->isleft && iter->pair->inResult)) {
            resultEvents.push_back(iter);
        }
    }

    // Due to overlapping edges the resultEvents array can be not wholly sorted
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (size_t i = 0; i < resultEvents.size(); ++i) {
            if (i + 1 < resultEvents.size() && mEventCmp(resultEvents[i], resultEvents[i + 1])) {
                std::swap(resultEvents[i], resultEvents[i + 1]);
                sorted = false;
            }
        }
    }

    for (auto i = 0; i < resultEvents.size(); ++i) {
        resultEvents[i]->index = i;
        if (!resultEvents[i]->isleft) {
            std::swap(resultEvents[i]->index, resultEvents[i]->pair->index);
        }
    }

    int (*nextIndexFunc)(int, const std::vector<SweepEvent *> &, const std::vector<bool> &) = nextIndex;
    std::vector<bool> processed(resultEvents.size(), false);
    std::vector<int> depth;
    std::vector<int> holeOf;
    std::vector<ResultContour<T>> tmpResult;

    ResultContour<T>* childPtr;
    for (auto i = 0; i < resultEvents.size(); ++i) {
        if (processed[i])
            continue;
        ResultContour<T> c;
        tmpResult.push_back(c);
        auto &contour = tmpResult.back();
        size_t contourId = tmpResult.size() - 1;
        depth.push_back(0);
        holeOf.push_back(-1);
        if (resultEvents[i]->prevInResult) {
            auto lowerContourId = resultEvents[i]->prevInResult->contourId;
            if (!resultEvents[i]->prevInResult->resultInOut) {
                tmpResult[lowerContourId].children.push_back(std::pair(contourId, childPtr));
                holeOf[contourId] = lowerContourId;
                depth[contourId] = depth[lowerContourId] + 1;
                contour.external = false;
            } else if (!tmpResult[lowerContourId].external) {
                tmpResult[holeOf[lowerContourId]].children.push_back(std::pair(contourId, childPtr));
                holeOf[contourId] = holeOf[lowerContourId];
                depth[contourId] = depth[lowerContourId];
                contour.external = false;
            }
        }
        int index = i;
        jereal angle = static_cast<jereal>(0);
        Point<T> initial_point(resultEvents[i]->point);
        polyline::move_to(contour.path, px(initial_point), py(initial_point));
        while (point::not_equal(resultEvents[index]->pair->point, initial_point)) {
            processed[index] = true;
            if (resultEvents[index]->isleft) {
                resultEvents[index]->resultInOut = false;
                resultEvents[index]->contourId = contourId;
            } else {
                resultEvents[index]->pair->resultInOut = true;
                resultEvents[index]->pair->contourId = contourId;
            }
            processed[index = resultEvents[index]->index] = true;
            angle = resultEvents[index]->edge.angle;
            if (resultEvents[index]->isleft)
                angle = -angle;
            polyline::pushback_vertex(contour.path,
                                      Vertex<T>(px(resultEvents[index]->point), py(resultEvents[index]->point), angle));
            index = nextIndexFunc(index, resultEvents, processed);
            if(index == -1)
                break;
        }
        if(index != -1)
        {
            // 如果为闭合图形需补上最后一个点
            processed[index] = processed[resultEvents[index]->index] = true;
            resultEvents[index]->pair->resultInOut = true;
            resultEvents[index]->pair->contourId = contourId;
            angle = resultEvents[index]->edge.angle;
            if (!resultEvents[index]->isleft)
                angle = -angle;
            polyline::pushback_vertex(contour.path,
                                      Vertex<T>(px(initial_point), py(initial_point), angle));
        }
        // 根据图形是否为孔转换点的连接方向
        if (depth[contourId] & 1)
        {
            contour.external = false;
            if(!contour.isCw())
                contour.reverseOrientation();
        }
        else
        {
            contour.external = true;
            if(contour.isCw())
                contour.reverseOrientation();
        }
    }

    for (auto i = 0; i < tmpResult.size(); ++i) {
        if(!tmpResult[i].external)
            continue;
        for (auto j = tmpResult[i].children.begin(); j != tmpResult[i].children.end(); j++)
        {
            j->second = &tmpResult[j->first];
        }
    }

    std::vector<Polygon<T>> result;
    for (auto i = 0; i < tmpResult.size(); ++i) {
        if (tmpResult[i].external) {
            result.push_back(tmpResult[i].toSurface());
        }
    }

    return result;
}

template<typename T>
JePolygonBoolOp<T>::JePolygonBoolOp(const Polygon<T> &subj,
                                    const Polygon<T> &clip,
                                    BooleanOpType op)
    : mSubject(subj)
    , mClipping(clip)
    , mOperation(op)
{}

template<typename T>
JePolygonBoolOp<T>::~JePolygonBoolOp() {}

template<typename T>
std::vector<Polygon<T>> JePolygonBoolOp<T>::run(Rect<T> subj_box, Rect<T> clip_box)
{
    // 将polygon中的顶点创建成线段事件保存至了eventQueue的优先队列中
    for (auto path : mSubject) {
        for (size_t j = 1; j < polyline::verteics_count(path); ++j) {
            auto e = Edge(polyline::vertex_at(path, j - 1), polyline::vertex_at(path, j));
            auto left_evt = store_event(new SweepEvent(true, e.ps, e, SUBJECT));
            auto right_evt = store_event(new SweepEvent(false, e.pe, e, SUBJECT));
            right_evt->pair = left_evt;
            left_evt->pair = right_evt;
            this->mEvtQueue.push(left_evt);
            this->mEvtQueue.push(right_evt);
        }
    }

    for (auto path : mClipping) {
        for (size_t j = 1; j < polyline::verteics_count(path); ++j) {
            auto e = Edge(polyline::vertex_at(path, j - 1), polyline::vertex_at(path, j));
            auto left_evt = store_event(new SweepEvent(true, e.ps, e, CLIPPING));
            auto right_evt = store_event(new SweepEvent(false, e.pe, e, CLIPPING));
            right_evt->pair = left_evt;
            left_evt->pair = right_evt;
            this->mEvtQueue.push(left_evt);
            this->mEvtQueue.push(right_evt);
        }
    }

    jereal min_max_x = jemath::jemin(px2(subj_box), px2(clip_box));
    typename std::set<SweepEvent *, EdgeCompare>::iterator curit, previt, nextit;
    while (!mEvtQueue.empty()) {
        auto evt = mEvtQueue.top();
        if ((mOperation == INTERSECTION && px(evt->point) - min_max_x > 100)
            || (mOperation == DIFFERENCE && px(evt->point) - px2(subj_box) > 100)) {
            // 如果是求交集，且当前事件点的x坐标大于两个多边形的最大x坐标，则直接返回
            // 如果是求差集，且当前事件点的x坐标大于subject的最大x坐标，则直接返回
            return connectEdges();
        }
        mSortedEvents.push_back(evt);

        mEvtQueue.pop();
        if (evt->isleft) {
            // 将左事件插入扫描线列表中，并查找左右相邻的事件
            Point<T> s = evt->edge.ps;
            Point<T> e = evt->edge.pe;
            qDebug() << Qt::endl << evt->polytype << "insert: ps(" << px(s) << "," << py(s) << ") pe(" << px(e) << "," << py(e)
                     << ") angle:" << evt->edge.angle << Qt::endl << "res:";

            auto debug = mSweepLines.insert(evt);
            curit = previt = nextit = evt->slit = debug.first;

            for(auto i = mSweepLines.begin(); i != mSweepLines.end(); i++)
            {
                Point<T> s = (*i)->edge.ps;
                Point<T> e = (*i)->edge.pe;
                qDebug() << (*i)->polytype << "ps(" << px(s) << "," << py(s) << ") pe(" << px(e) << "," << py(e)
                         << ") angle:" << (*i)->edge.angle;
            }

            (previt != mSweepLines.begin()) ? --previt : previt = mSweepLines.end();
            ++nextit;
            calcEventProps(evt, previt);

            // 检查左右相邻的事件是否与当前事件有交点
            if (nextit != mSweepLines.end()) {
                if (checkIntersection(evt, *nextit) == 2) {
                    calcEventProps(evt, previt);
                    calcEventProps(*nextit, curit);
                }
            }
            if (previt != mSweepLines.end()) {
                if (checkIntersection(evt, *previt) == 2) {
                    typename std::set<SweepEvent *, EdgeCompare>::iterator previt_prev = previt;
                    (previt_prev != mSweepLines.begin()) ? --previt_prev
                                                         : previt_prev = mSweepLines.end();
                    calcEventProps(*previt, previt_prev);
                    calcEventProps(evt, previt);
                }
            }
        } else {
            evt = evt->pair; // 如果是右事件，则转换为操作左事件
            curit = nextit = previt = evt->slit;
            (previt != mSweepLines.begin()) ? --previt : previt = mSweepLines.end();
            ++nextit;

            Point<T> s = evt->edge.ps;
            Point<T> e = evt->edge.pe;
            qDebug() << Qt::endl << (*curit)->polytype << "erase: ps(" << px(s) << "," << py(s) << ") pe(" << px(e) << "," << py(e)
                     << ") angle:" << evt->edge.angle << Qt::endl << "res:";

            mSweepLines.erase(curit);

            for(auto i = mSweepLines.begin(); i != mSweepLines.end(); i++)
            {
                Point<T> s = (*i)->edge.ps;
                Point<T> e = (*i)->edge.pe;
                qDebug() << (*i)->polytype << "ps(" << px(s) << "," << py(s) << ") pe(" << px(e) << "," << py(e)
                         << ") angle:" << (*i)->edge.angle;
            }

            if (previt != mSweepLines.end() && nextit != mSweepLines.end()) {
                checkIntersection(*previt, *nextit);
            }
        }
    }

    return connectEdges();
}

} // internal


namespace boolop {


template<typename T>
std::vector<Polygon<T>> polygons_intersection(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b)
{
    Rect<T> subj_box = polygon::get_bound_rect(polygon_a);
    Rect<T> clip_box = polygon::get_bound_rect(polygon_b);

    // 有一个多边形为空时，可直接返回
    if (polygon_a.size() * polygon_b.size() == 0) {
        return std::vector<Polygon<T>>();
    }

    // 两图形不相交可以不进行扫描直接生成结果
    if (!boolop_internal::intersects_rect2rect(subj_box, clip_box)) {
        return std::vector<Polygon<T>>();
    }
    jegeo::boolop_internal::JePolygonBoolOp<T> bp(polygon_a, polygon_b, boolop_internal::INTERSECTION);
    return bp.run(subj_box, clip_box);
}

template<typename T>
std::vector<Polygon<T>> polygons_union(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b)
{
    Rect<T> subj_box = polygon::get_bound_rect(polygon_a);
    Rect<T> clip_box = polygon::get_bound_rect(polygon_b);

    // 有一个多边形为空时，可直接返回
    if (polygon_a.size() * polygon_b.size() == 0) {
        return (polygon_a.size() == 0) ? std::vector<Polygon<T>>{polygon_b} : std::vector<Polygon<T>>{polygon_a};
    }

    // 两图形不相交可以不进行扫描直接生成结果
    if (!boolop_internal::intersects_rect2rect(subj_box, clip_box)) {
        return std::vector<Polygon<T>>{polygon_a, polygon_b};
    }
    jegeo::boolop_internal::JePolygonBoolOp<T> bp(polygon_a, polygon_b, boolop_internal::UNION);
    return bp.run(subj_box, clip_box);
}

template<typename T>
std::vector<Polygon<T>> polygons_difference(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b)
{
    Rect<T> subj_box = polygon::get_bound_rect(polygon_a);
    Rect<T> clip_box = polygon::get_bound_rect(polygon_b);

    // 有一个多边形为空时，可直接返回
    if (polygon_a.size() * polygon_b.size() == 0) {
        return std::vector<Polygon<T>>{polygon_a};
    }

    // 两图形不相交可以不进行扫描直接生成结果
    if (!boolop_internal::intersects_rect2rect(subj_box, clip_box)) {
        return std::vector<Polygon<T>>{polygon_a};
    }
    jegeo::boolop_internal::JePolygonBoolOp<T> bolop(polygon_a, polygon_b, boolop_internal::DIFFERENCE);
    return bolop.run(subj_box, clip_box);
}

template<typename T>
std::vector<Polygon<T>> polygons_xor(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b)
{
    Rect<T> subj_box = polygon::get_bound_rect(polygon_a);
    Rect<T> clip_box = polygon::get_bound_rect(polygon_b);

    // 有一个多边形为空时，可直接返回
    if (polygon_a.size() * polygon_b.size() == 0) {
        return (polygon_a.size() == 0) ? std::vector<Polygon<T>>{polygon_b} : std::vector<Polygon<T>>{polygon_a};
    }

    // 两图形不相交可以不进行扫描直接生成结果
    if (!boolop_internal::intersects_rect2rect(subj_box, clip_box)) {
       return std::vector<Polygon<T>>{polygon_a, polygon_b};
    }
    jegeo::boolop_internal::JePolygonBoolOp<T> bolop(polygon_a, polygon_b, boolop_internal::XOR);
    return bolop.run(subj_box, clip_box);
}

} //

} // jegeo

#endif // JEGEO_POLYBOOLOP_HPP
